package org.example;

import java.util.Iterator;
import java.util.function.Consumer;

import org.jetbrains.annotations.NotNull;

/**
 * @Author xhw
 * @Date 2023/11/5
 * @Version 1.0
 */
//创建一个链表，实现两个方向的迭代
public class LinkList<T> implements Iterable<T> {
    //定义头节点
    private Node<T> head;
    //定义尾节点
    private Node<T> last;

    //从头开始添加
    public void addFirst(final T val) {
        //新建一个当前节点
        Node<T> newNode = new Node<>(val);
        if (head == null) {
            head = newNode;
            last = head;
        } else {
            //让当前节点的下一个引用指向原节点的头
            newNode.next = head;
            //让原节点的头指向当前节点
            head.pre = newNode;
            //更新现在的头节点
            head = newNode;
        }
    }

    //根据indax的值来进行指定添加节点
    public void addIndex(int index, T val) {
        //先判断index是否合法
        if (index < 0 || index > size()) {
            System.out.println("下标越界欸");
        }
        //合法的话那么就进行判断特殊值
        //头插
        if (index == 0) {
            addFirst(val);
        }
        //尾插
        if (index == size()) {
            addLast(val);
        }
        //如果不是特殊值那就创建一个新的node然后设置当前节点为头之后通过index进行移动，将当前节点移动到指定节点
        Node<T> newNode = new Node<>(val);
        Node<T> currentNode = head;
        while (index > 0) {
            currentNode = currentNode.next;
            index--;
        }
        //在前一个节点插入
        newNode.next = currentNode;
        newNode.pre = currentNode.pre;
        // 修改前一个节点的 next 属性
        currentNode.pre.next = newNode;
        // 修改当前节点的 pre 属性
        currentNode.pre = newNode;
    }

    //从尾部添加
    public void addLast(final T val) {
        Node<T> newNode = new Node<>(val);
        if (head == null) {
            head = newNode;
            last = head;
        } else {
            //让最后节点指向当前节点
            last.next = newNode;
            //让当前节点的上一个节点指向原尾节点
            newNode.pre = last;
            //更新现在的尾节点
            last = newNode;
        }
    }

    //从右往左输出
    public void backward() {
        Node<T> currentNode = last;
        while (currentNode != null) {
            System.out.print(currentNode.val + "<---");
            currentNode = currentNode.pre;
        }
        System.out.println();
    }

    //清空
    public void clear() {
        head = null;
        last = null;
    }

    //查找特定值
    public int find(T key) {
        Node<T> currentNode = head;
        int index = 0;
        while (currentNode != null) {
            if (currentNode.val.equals(key)) {
                System.out.println("找到" + key + "的位置" + index);
                return index;
            }
            currentNode = currentNode.next;
            index++;
        }
        System.out.println("没有找到值为 " + key + " 的节点");
        //都没找到就返回-1
        return -1;
    }

    //从左往右迭代输出
    public void forward(final Consumer<T> consumer) {
        var itr = new Itr();
        while (itr.hasNext()) {
            consumer.accept(itr.next());
        }
    }

    public Iterator<T> getBackItr() {
        return new Itr(false);
    }

    public Iterator<T> getForwardItr() {
        return new Itr(true);
    }

    @NotNull
    @Override
    public Iterator<T> iterator() {
        return new Itr();
    }

    //删除节点
    public boolean remove(T key) {
        //先查询有没有key值，有进行删除
        int index = find(key);
        //如果有值
        if (index != -1) {
            //根据索引删除
            removeByIndex(index);
            //再找一次
            int nowIndex = find(key);
            //如果还有
            if (nowIndex != -1) {
                //调用自己
                return remove(key);
            } else {
                //删除完毕
                return true;
            }

        } else {
            System.out.println("没有找到" + key);
            return false;
        }
    }

    //还需要根据size来进行数组长度的判断
    public int size() {
        //计数器
        int size = 0;
        //设置当前节点为current
        Node<T> current = head;
        //进行计数
        while (current != null) {
            current = current.next;
            size++;
        }
        return size;

    }

    //根据索引删除节点
    private boolean removeByIndex(int index) {
        //获取长度
        int size = size();
        //判断是否合法
        if (index < 0 || index >= size) {
            return false;
        }
        //如果是头指针
        if (index == 0) {
            //删除头指针，指向下一个节点
            head = head.next;
            //下一个节点有值
            if (head != null) {
                head.pre = null;
                //下一个节点没有值
            } else {
                last = head;
            }
            size--;
            return true;
        }
        //如果是尾节点节点
        if (index == size - 1) {
            last = last.pre;
            last.next = null;
            size--;
            return true;
        }
        //如果是普通节点
        Node<T> currentNode = head;
        for (int i = 0; i < index; i++) {
            //让当前节点转到需要删除的节点
            currentNode = currentNode.next;
        }
        //将当前节点的前驱节点的后继节点指向当前节点的后继节点
        currentNode.pre.next = currentNode.next;
        //将当前节点的后继节点的前驱节点指向当前节点的前驱节点
        currentNode.next.pre = currentNode.pre;
        size--;
        return true;
    }


    //迭代LinkList实例，可以当成一个游标
    private class Itr implements Iterator<T> {

        private final boolean forward;
        //定义一个游标，并初始化指向链表头|表尾
        private Node<T> current;

        private Itr() {
            this(true);
        }

        private Itr(final boolean forward) {
            this.forward = forward;
            if (forward) {
                current = LinkList.this.head;
            } else {
                current = LinkList.this.last;
            }
        }

        @Override
        public boolean hasNext() {
            //当前游标是否指向有效节点
            return current != null;
        }

        @Override
        public T next() {
            //返回当前游标的Node,并且移动游标
            final T val = current.val;

            if (forward) {
                current = current.next;
            } else {
                current = current.pre;
            }

            return val;
        }
    }
}

